<!DOCTYPE html>



  


<html class="theme-next mist use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="Hexo, NexT">










<meta name="description" content="在平凡的生活里做着平凡的事，愿我造就不平凡的未来。">
<meta property="og:type" content="website">
<meta property="og:title" content="平凡小札">
<meta property="og:url" content="http://yoursite.com/index.html">
<meta property="og:site_name" content="平凡小札">
<meta property="og:description" content="在平凡的生活里做着平凡的事，愿我造就不平凡的未来。">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="平凡小札">
<meta name="twitter:description" content="在平凡的生活里做着平凡的事，愿我造就不平凡的未来。">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Mist',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://yoursite.com/">





  <title>平凡小札</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <a href="https://github.com/SimFG/SimFG.github.io"><img style="position: absolute; top: 0; right: 0;" width="149" height="149" src="https://github.blog/wp-content/uploads/2008/12/forkme_right_white_ffffff.png?resize=149%2C149" class="attachment-full size-full" alt="Fork me on GitHub" data-recalc-dims="1"></a>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">平凡小札</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/11/20/LeetCode-39/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="影决">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平凡小札">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2019/11/20/LeetCode-39/" itemprop="url">LeetCode-39</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-11-20T23:56:42+08:00">
                2019-11-20
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/算法/" itemprop="url" rel="index">
                    <span itemprop="name">算法</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h2 id="A039-Combination-Sum"><a href="#A039-Combination-Sum" class="headerlink" title="A039  Combination Sum"></a>A039  Combination Sum</h2><p><a href="https://leetcode-cn.com/problems/combination-sum/" target="_blank" rel="noopener">原文链接</a></p>
<pre><code>Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]</code></pre><p>分析： </p>
<pre><code>思路
    1. 找出数组中最多多少元素可以组成target
    2. 如果给定一个数目，也就是说找出数组中确切个数的元素来组成target
    3. 去重</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="keyword">public</span> List&lt;List&lt;Integer&gt;&gt; combinationSum(<span class="keyword">int</span>[] candidates, <span class="keyword">int</span> target) &#123;</span><br><span class="line">        <span class="keyword">if</span> (candidates.length == <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        Arrays.sort(candidates);</span><br><span class="line">        List&lt;List&lt;Integer&gt;&gt; res = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        <span class="keyword">int</span> maxCount = target / candidates[<span class="number">0</span>];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; maxCount; i++)&#123;</span><br><span class="line">            List&lt;List&lt;Integer&gt;&gt; tmp = getCombinationSum(candidates, target, i + <span class="number">1</span>);</span><br><span class="line">            <span class="keyword">if</span> (tmp != <span class="keyword">null</span>)</span><br><span class="line">                res.addAll(tmp);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        List&lt;List&lt;Integer&gt;&gt; removeTmp = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; res.size(); i++)&#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = i + <span class="number">1</span>; j &lt; res.size(); j++)&#123;</span><br><span class="line">                <span class="keyword">if</span> (res.get(i).size() != res.get(j).size())&#123;</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                List&lt;Integer&gt; ilist = res.get(i);</span><br><span class="line">                List&lt;Integer&gt; jlist = res.get(j);</span><br><span class="line">                <span class="keyword">if</span> (isSame(ilist, jlist))&#123;</span><br><span class="line">                    removeTmp.add(ilist);</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        res.removeAll(removeTmp);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isSame</span><span class="params">(List&lt;Integer&gt; a, List&lt;Integer&gt; b)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span>[] aint = <span class="keyword">new</span> <span class="keyword">int</span>[a.size()];</span><br><span class="line">        <span class="keyword">int</span>[] bint = <span class="keyword">new</span> <span class="keyword">int</span>[b.size()];</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; a.size(); i++)&#123;</span><br><span class="line">            aint[i] = a.get(i);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; b.size(); i++)&#123;</span><br><span class="line">            bint[i] = b.get(i);</span><br><span class="line">        &#125;</span><br><span class="line">        Arrays.sort(aint);</span><br><span class="line">        Arrays.sort(bint);</span><br><span class="line">        <span class="keyword">boolean</span> res = <span class="keyword">true</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; aint.length; i++)&#123;</span><br><span class="line">            <span class="keyword">if</span> (aint[i] != bint[i])&#123;</span><br><span class="line">                res = <span class="keyword">false</span>;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> List&lt;List&lt;Integer&gt;&gt; getCombinationSum(<span class="keyword">int</span>[] candidates, <span class="keyword">int</span> target, <span class="keyword">int</span> count)&#123;</span><br><span class="line">        <span class="keyword">if</span> (count == <span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">int</span> j = getIndex(candidates, target);</span><br><span class="line">            <span class="keyword">if</span> (j == -<span class="number">1</span>)</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">            List&lt;List&lt;Integer&gt;&gt; lists = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">            List&lt;Integer&gt;list2 = <span class="keyword">new</span> ArrayList&lt;&gt;(<span class="number">1</span>);</span><br><span class="line">            list2.add(candidates[j]);</span><br><span class="line">            lists.add(list2);</span><br><span class="line">            <span class="keyword">return</span> lists;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (count == <span class="number">2</span>)&#123;</span><br><span class="line">            List&lt;List&lt;Integer&gt;&gt; lists = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; candidates.length; i++)&#123;</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> j = i; j &lt; candidates.length; j++)&#123;</span><br><span class="line">                    <span class="keyword">if</span> (candidates[i] + candidates[j] == target)&#123;</span><br><span class="line">                        List&lt;Integer&gt;list2 = <span class="keyword">new</span> ArrayList&lt;&gt;(<span class="number">2</span>);</span><br><span class="line">                        list2.add(candidates[i]);</span><br><span class="line">                        list2.add(candidates[j]);</span><br><span class="line">                        lists.add(list2);</span><br><span class="line">                    &#125;<span class="keyword">else</span> <span class="keyword">if</span> (candidates[i] + candidates[j] &gt; target)&#123;</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    &#125;</span><br><span class="line"></span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> lists;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (count == <span class="number">3</span>)&#123;</span><br><span class="line">            List&lt;List&lt;Integer&gt;&gt; lists = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; candidates.length; i++)&#123;</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> j = i; j &lt; candidates.length; j++)&#123;</span><br><span class="line">                    <span class="keyword">for</span> (<span class="keyword">int</span> k = j; k &lt; candidates.length; k++) &#123;</span><br><span class="line">                        <span class="keyword">if</span> (candidates[i] + candidates[j] + candidates[k] == target) &#123;</span><br><span class="line">                            List&lt;Integer&gt; list2 = <span class="keyword">new</span> ArrayList&lt;&gt;(<span class="number">2</span>);</span><br><span class="line">                            list2.add(candidates[i]);</span><br><span class="line">                            list2.add(candidates[j]);</span><br><span class="line">                            list2.add(candidates[k]);</span><br><span class="line">                            lists.add(list2);</span><br><span class="line">                        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (candidates[i] + candidates[j] + candidates[k] &gt; target) &#123;</span><br><span class="line">                            <span class="keyword">break</span>;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> lists;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        List&lt;List&lt;Integer&gt;&gt; res = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; candidates.length; i++)&#123;</span><br><span class="line">            List&lt;List&lt;Integer&gt;&gt; list = getCombinationSum(candidates, target - candidates[i], count - <span class="number">1</span>);</span><br><span class="line">            <span class="keyword">if</span> (list != <span class="keyword">null</span>)&#123;</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; list.size(); j++)&#123;</span><br><span class="line">                    List&lt;Integer&gt; tmp = list.get(j);</span><br><span class="line">                    tmp.add(candidates[i]);</span><br><span class="line">                &#125;</span><br><span class="line">                res.addAll(list);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getIndex</span><span class="params">(<span class="keyword">int</span>[] candidates, <span class="keyword">int</span> target)</span></span>&#123;</span><br><span class="line">        <span class="comment">// 2 3 5</span></span><br><span class="line">        <span class="comment">// 0 3 1</span></span><br><span class="line">        <span class="comment">// 0 0 1</span></span><br><span class="line">        <span class="keyword">int</span> start = <span class="number">0</span>, end = candidates.length, middle = (end + start) / <span class="number">2</span>;</span><br><span class="line">        <span class="keyword">while</span> (start &lt; end - <span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span> (candidates[middle] == target)&#123;</span><br><span class="line">                <span class="keyword">return</span> middle;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (candidates[middle] &lt; target)&#123;</span><br><span class="line">                start = middle;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                end = middle;</span><br><span class="line">            &#125;</span><br><span class="line">            middle = (end + start) / <span class="number">2</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (candidates[start] == target)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span>  -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>




          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/11/19/LeetCode-37/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="影决">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平凡小札">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2019/11/19/LeetCode-37/" itemprop="url">LeetCode-37</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-11-19T23:56:42+08:00">
                2019-11-19
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/算法/" itemprop="url" rel="index">
                    <span itemprop="name">算法</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h2 id="A037-Sudoku-Solver"><a href="#A037-Sudoku-Solver" class="headerlink" title="A037  Sudoku Solver"></a>A037  Sudoku Solver</h2><p><a href="https://leetcode-cn.com/problems/sudoku-solver/" target="_blank" rel="noopener">原文链接</a></p>
<pre><code>Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character &apos;.&apos;.

Note:
The given board contain only digits 1-9 and the character &apos;.&apos;.
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.</code></pre><p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png" alt="图片"></p>
<p><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png" alt="图片"></p>
<p>分析： </p>
<pre><code>方法
    1. getCandidates方法：获取当前位置可填字符
    2. findNext方法：获取下一个需要填写的空格位置
    3. backtrack方法：回溯方法

变量
    1. trace：类型Stack&lt;int[]&gt;，其数组中为第一个行号，第一个列号
    2. allCandidate：二维数组，存储着每一个需要填写的空格中可填字符
    3. next：存储下一个字符的位置

思路
    1. 当findNext找不到下一个字符的填写位置则表示完成数独
    2. 找到下一个可选的字符的位置，然后找到该位置可填写的字符
    3. 如果存在候选字符，则选择该候选字符数组中选择最后一个，然后将该位置压入栈中，更新next
    4. 如果没有候选字符，则表示之前填写的存在问题，则调用回溯方法，弹出栈顶元素，然后将next赋予弹出的值，并将元素设置为空</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">solveSudoku</span><span class="params">(<span class="keyword">char</span>[][] board)</span> </span>&#123;</span><br><span class="line">        Stack&lt;<span class="keyword">int</span>[]&gt; trace = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">        <span class="comment">// 当前排除元素</span></span><br><span class="line">        <span class="comment">// char[][] excludes = new char[81][1];</span></span><br><span class="line">        <span class="comment">// 存储候选</span></span><br><span class="line">        <span class="keyword">char</span>[][] allCandidate = <span class="keyword">new</span> <span class="keyword">char</span>[<span class="number">81</span>][<span class="number">9</span>];</span><br><span class="line">        <span class="comment">// char[][] cacheCandidate = new char[81][9];</span></span><br><span class="line">        <span class="keyword">int</span> i = <span class="number">0</span>, j = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span>[] next = findNext(board, i, j);</span><br><span class="line">        <span class="keyword">int</span> mn = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span> (next[<span class="number">0</span>]!= -<span class="number">1</span> &amp;&amp; i &lt; <span class="number">9</span> &amp;&amp; j &lt; <span class="number">9</span>)&#123;</span><br><span class="line">            <span class="keyword">int</span> row = next[<span class="number">0</span>];</span><br><span class="line">            <span class="keyword">int</span> col = next[<span class="number">1</span>];</span><br><span class="line">            allCandidate[<span class="number">9</span> * row + col] = getCandidates(board, row, col, allCandidate);</span><br><span class="line">            <span class="keyword">char</span>[] candidates = allCandidate[<span class="number">9</span> * row + col];</span><br><span class="line"><span class="comment">//            mn++;</span></span><br><span class="line"><span class="comment">//            if (candidates.length != 0)&#123;</span></span><br><span class="line"><span class="comment">//                System.out.println(Arrays.toString(candidates));</span></span><br><span class="line"><span class="comment">//                System.out.println(row + ":" + col);</span></span><br><span class="line"><span class="comment">//                System.out.println(mn);</span></span><br><span class="line"><span class="comment">//            &#125;</span></span><br><span class="line">            <span class="keyword">if</span> (candidates.length == <span class="number">0</span>)&#123;</span><br><span class="line">                <span class="comment">// 回溯</span></span><br><span class="line">                <span class="keyword">int</span>[] prev = backtrack(trace);</span><br><span class="line">                <span class="keyword">if</span> (prev[<span class="number">0</span>] == -<span class="number">1</span>)&#123;</span><br><span class="line">                    i = <span class="number">0</span>; j =<span class="number">0</span>;</span><br><span class="line">                &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                    i = prev[<span class="number">0</span>]; j = prev[<span class="number">1</span>];</span><br><span class="line">                &#125;</span><br><span class="line">                next = <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;i, j&#125;;</span><br><span class="line">                board[i][j] = <span class="string">'.'</span>;</span><br><span class="line"></span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">// 每次取最后一个，当回溯时直接从候选中删除最后一个</span></span><br><span class="line">                board[row][col] = candidates[candidates.length - <span class="number">1</span>];</span><br><span class="line">                trace.push(<span class="keyword">new</span> <span class="keyword">int</span>[]&#123;row, col&#125;);</span><br><span class="line">                i = row; j = col;</span><br><span class="line">                next = findNext(board, i, j);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">int</span>[] backtrack(Stack&lt;<span class="keyword">int</span>[]&gt; trace)&#123;</span><br><span class="line">        <span class="keyword">if</span> (trace.empty())&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;-<span class="number">1</span>, -<span class="number">1</span>&#125;;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> trace.pop();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 获取下一个需要填充的位置</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">int</span>[] findNext(<span class="keyword">char</span>[][] board, <span class="keyword">int</span> row, <span class="keyword">int</span> col)&#123;</span><br><span class="line">        <span class="keyword">int</span>[] result = <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;-<span class="number">1</span>, -<span class="number">1</span>&#125;;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = col; i &lt; <span class="number">9</span>; i++)&#123;</span><br><span class="line">            <span class="keyword">if</span> (board[row][i] == <span class="string">'.'</span>)&#123;</span><br><span class="line">                result[<span class="number">0</span>] = row;</span><br><span class="line">                result[<span class="number">1</span>] = i;</span><br><span class="line">                <span class="comment">// System.out.println(Arrays.toString(result));</span></span><br><span class="line">                <span class="keyword">return</span> result;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = row + <span class="number">1</span>; i &lt; <span class="number">9</span>; i++)&#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; <span class="number">9</span>; j++)&#123;</span><br><span class="line">                <span class="keyword">if</span> (board[i][j] == <span class="string">'.'</span>)&#123;</span><br><span class="line">                    result[<span class="number">0</span>] = i;</span><br><span class="line">                    result[<span class="number">1</span>] = j;</span><br><span class="line">                    <span class="comment">// System.out.println(Arrays.toString(result));</span></span><br><span class="line">                    <span class="keyword">return</span> result;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 获取当前元素可选值</span></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">char</span>[] getCandidates(<span class="keyword">char</span>[][] board, <span class="keyword">int</span> row, <span class="keyword">int</span> col, <span class="keyword">char</span>[][] allCandidate)&#123;</span><br><span class="line">        <span class="keyword">char</span>[] cache = allCandidate[<span class="number">9</span> * row + col];</span><br><span class="line">        <span class="keyword">int</span> cacheLen = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; cache.length; i++)&#123;</span><br><span class="line">            <span class="keyword">if</span> (cache[i] != <span class="string">'\0'</span>)&#123;</span><br><span class="line">                cacheLen ++;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (cacheLen &gt; <span class="number">1</span>)&#123;</span><br><span class="line">            <span class="comment">// char[] exclude = excludes[9 * row + col];</span></span><br><span class="line">            <span class="keyword">return</span> Arrays.copyOf(cache, cacheLen - <span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (cacheLen == <span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">char</span>[<span class="number">0</span>];</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 缓存</span></span><br><span class="line"><span class="comment">//        cache = cacheCandidate[9 * row + col];</span></span><br><span class="line"><span class="comment">//        cacheLen = 0;</span></span><br><span class="line"><span class="comment">//        for (int i = 0; i &lt; cache.length; i++)&#123;</span></span><br><span class="line"><span class="comment">//            if (cache[i] != '\0')&#123;</span></span><br><span class="line"><span class="comment">//                cacheLen ++;</span></span><br><span class="line"><span class="comment">//            &#125;else &#123;</span></span><br><span class="line"><span class="comment">//                break;</span></span><br><span class="line"><span class="comment">//            &#125;</span></span><br><span class="line"><span class="comment">//        &#125;</span></span><br><span class="line"><span class="comment">//        if (cacheLen != 0)&#123;</span></span><br><span class="line"><span class="comment">//            return cache;</span></span><br><span class="line"><span class="comment">//        &#125;</span></span><br><span class="line"></span><br><span class="line">        <span class="keyword">char</span>[] result = <span class="keyword">new</span> <span class="keyword">char</span>[<span class="number">9</span>];</span><br><span class="line">        <span class="keyword">int</span> len = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">boolean</span>[] test = <span class="keyword">new</span> <span class="keyword">boolean</span>[<span class="number">9</span>];</span><br><span class="line">        <span class="comment">// row</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; <span class="number">9</span>; i++)&#123;</span><br><span class="line">            <span class="keyword">if</span> (i == col)</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            <span class="keyword">char</span> c = board[row][i];</span><br><span class="line">            <span class="keyword">if</span> (c != <span class="string">'.'</span>)&#123;</span><br><span class="line">                <span class="keyword">int</span> index = c - <span class="string">'1'</span>;</span><br><span class="line">                test[index] = <span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// col</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; <span class="number">9</span>; i++)&#123;</span><br><span class="line">            <span class="keyword">if</span> (i == row)</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            <span class="keyword">char</span> c = board[i][col];</span><br><span class="line">            <span class="keyword">if</span> (c != <span class="string">'.'</span>)&#123;</span><br><span class="line">                <span class="keyword">int</span> index = c - <span class="string">'1'</span>;</span><br><span class="line">                test[index] = <span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 3 * 3</span></span><br><span class="line">        <span class="keyword">int</span> x = row / <span class="number">3</span>;</span><br><span class="line">        <span class="keyword">int</span> y = col / <span class="number">3</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; <span class="number">3</span>; i++)&#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; <span class="number">3</span>; j++)&#123;</span><br><span class="line">                <span class="keyword">int</span> a = <span class="number">3</span> * x + i;</span><br><span class="line">                <span class="keyword">int</span> b = <span class="number">3</span> * y + j;</span><br><span class="line">                <span class="keyword">if</span> (a == row &amp;&amp; b == col)&#123;</span><br><span class="line">                    <span class="keyword">continue</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">char</span> c = board[a][b];</span><br><span class="line">                <span class="keyword">if</span> (c != <span class="string">'.'</span>)&#123;</span><br><span class="line">                    <span class="keyword">int</span> index = c - <span class="string">'1'</span>;</span><br><span class="line">                    test[index] = <span class="keyword">true</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; test.length; i++)&#123;</span><br><span class="line">            <span class="keyword">if</span> (!test[i])&#123;</span><br><span class="line">                result[len] = (<span class="keyword">char</span>) (<span class="string">'1'</span> + i);</span><br><span class="line">                len++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> Arrays.copyOf(result, len);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>




          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/11/18/LeetCode-35/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="影决">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平凡小札">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2019/11/18/LeetCode-35/" itemprop="url">LeetCode-35</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-11-18T23:56:42+08:00">
                2019-11-18
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/算法/" itemprop="url" rel="index">
                    <span itemprop="name">算法</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h2 id="A035-Search-Insert-Position"><a href="#A035-Search-Insert-Position" class="headerlink" title="A035  Search Insert Position"></a>A035  Search Insert Position</h2><p><a href="https://leetcode-cn.com/problems/search-insert-position/" target="_blank" rel="noopener">原文链接</a></p>
<pre><code>Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0</code></pre><p>分析： </p>
<pre><code>1. 二分查找，具体见注解</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">searchInsert</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> start = <span class="number">0</span>, end = nums.length, result = (start + end) / <span class="number">2</span>;</span><br><span class="line">        <span class="keyword">while</span> (start &lt; end - <span class="number">1</span>)&#123;</span><br><span class="line">            <span class="comment">// nums 存在值为target的元素</span></span><br><span class="line">            <span class="keyword">if</span> (nums[result] == target)&#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 遍历到end，都未找到，且最后一个元素的值都没有target大</span></span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (result + <span class="number">1</span> == end &amp;&amp; nums[result] &lt; target)&#123;</span><br><span class="line">                result = end;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 开头元素都比target大</span></span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (result == start &amp;&amp; nums[result] &gt; target)&#123;</span><br><span class="line">                result = start;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span> (nums[result] &gt; target)&#123;</span><br><span class="line">                end = result;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (nums[result] &lt; target)&#123;</span><br><span class="line">                start = result;</span><br><span class="line">            &#125;</span><br><span class="line">            result = (start + end) / <span class="number">2</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 处理不存在的情况，且目标值存在与两个元素之间</span></span><br><span class="line">        <span class="keyword">if</span> (start == end - <span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span> (nums[start] &lt; target)&#123;</span><br><span class="line">                result ++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// System.out.println(result);</span></span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>




          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/11/17/LeetCode-34/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="影决">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平凡小札">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2019/11/17/LeetCode-34/" itemprop="url">LeetCode-34</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-11-17T23:56:42+08:00">
                2019-11-17
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/算法/" itemprop="url" rel="index">
                    <span itemprop="name">算法</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h2 id="A034-Find-First-and-Last-Position-of-Element-in-Sorted-Array"><a href="#A034-Find-First-and-Last-Position-of-Element-in-Sorted-Array" class="headerlink" title="A034  Find First and Last Position of Element in Sorted Array"></a>A034  Find First and Last Position of Element in Sorted Array</h2><p><a href="https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/" target="_blank" rel="noopener">原文链接</a></p>
<pre><code>Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0</code></pre><p>分析： </p>
<pre><code>1. 找出最靠后的一个与target值相同的元素，也就是该元素值等于target且小于后一个元素
2. 找出最靠前的一个与target值相同的元素，也就是该元素值等于target且大于前一个元素</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">int</span>[] searchRange(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123;</span><br><span class="line">        <span class="keyword">if</span> (nums.length == <span class="number">0</span>) <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;-<span class="number">1</span>, -<span class="number">1</span>&#125;;</span><br><span class="line">        <span class="keyword">int</span> a = findMax(nums, target);</span><br><span class="line">        <span class="keyword">int</span> b = findMin(nums, target);</span><br><span class="line">        <span class="keyword">int</span>[] result = <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;b, a&#125;;</span><br><span class="line">        System.out.println(b + <span class="string">","</span> + a);</span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findMax</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> start = <span class="number">0</span>, end = nums.length, result = (start + end) / <span class="number">2</span>;</span><br><span class="line">        <span class="keyword">while</span> (start &lt; end - <span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span> (nums[result] == target &amp;&amp; result + <span class="number">1</span> == end)&#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (result + <span class="number">1</span> == end &amp;&amp; nums[result] == target &amp;&amp; nums[result + <span class="number">1</span>] &gt; target)&#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (nums[result] &gt; target)&#123;</span><br><span class="line">                end = result;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                start = result;</span><br><span class="line">            &#125;</span><br><span class="line">            result = (start + end) / <span class="number">2</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (nums[result] != target)</span><br><span class="line">            <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findMin</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> start = <span class="number">0</span>, end = nums.length, result = (start + end) / <span class="number">2</span>;</span><br><span class="line">        <span class="keyword">while</span> (start &lt; end - <span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span> (nums[result] == target &amp;&amp; result == start)&#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (nums[result] == target &amp;&amp; nums[result - <span class="number">1</span>] &lt; target)&#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (nums[result] &lt; target)&#123;</span><br><span class="line">                start = result;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                end = result;</span><br><span class="line">            &#125;</span><br><span class="line">            result = (start + end) / <span class="number">2</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (nums[result] != target)</span><br><span class="line">            <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>




          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/11/16/LeetCode-33/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="影决">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平凡小札">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2019/11/16/LeetCode-33/" itemprop="url">LeetCode-33</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-11-16T23:56:42+08:00">
                2019-11-16
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/算法/" itemprop="url" rel="index">
                    <span itemprop="name">算法</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h2 id="A033-Search-in-Rotated-Sorted-Array"><a href="#A033-Search-in-Rotated-Sorted-Array" class="headerlink" title="A033 Search in Rotated Sorted Array"></a>A033 Search in Rotated Sorted Array</h2><p><a href="https://leetcode-cn.com/problems/search-in-rotated-sorted-array/submissions/" target="_blank" rel="noopener">原文链接</a></p>
<pre><code>Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm&apos;s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1</code></pre><p>分析： </p>
<pre><code>1. 找出旋转点
    特殊情况：数组未旋转
2. 根据旋转点，将数组切分为两个进行二分查找
    特殊情况：
        数组未旋转，则初始化二分查找的首和尾进行处理；
        旋转后数组，数组第一个元素刚好为目标元素；</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">search</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> result = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span> (nums.length == <span class="number">0</span>) <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span> (nums.length == <span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span> (target == nums[<span class="number">0</span>])&#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">                <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> rotationIndex = findRotation(nums);</span><br><span class="line">        <span class="comment">// System.out.println(rotationIndex);</span></span><br><span class="line">        result = findResult(nums, rotationIndex, target);</span><br><span class="line"></span><br><span class="line">        <span class="comment">// System.out.println(result);</span></span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findResult</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> rotationIndex, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> start, end, result;</span><br><span class="line">        <span class="keyword">if</span> (rotationIndex == <span class="number">0</span>)&#123;</span><br><span class="line">            start = <span class="number">0</span>;</span><br><span class="line">            end = nums.length;</span><br><span class="line">        &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">if</span> (nums[<span class="number">0</span>] &lt; target)&#123;</span><br><span class="line">                start = <span class="number">0</span>;</span><br><span class="line">                end = rotationIndex;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (nums[<span class="number">0</span>] &gt; target)&#123;</span><br><span class="line">                start = rotationIndex;</span><br><span class="line">                end = nums.length;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        result = (start + end) / <span class="number">2</span>;</span><br><span class="line">        <span class="keyword">while</span> (start &lt; end - <span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span> (nums[result] == target)&#123;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (nums[result] &gt; target)&#123;</span><br><span class="line">                end = result;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (nums[result] &lt; target)&#123;</span><br><span class="line">                start = result;</span><br><span class="line">            &#125;</span><br><span class="line">            result = (start + end) / <span class="number">2</span>;</span><br><span class="line">            <span class="comment">// System.out.println(start+" "+end);</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (start == end - <span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span> (nums[start] != target)&#123;</span><br><span class="line">                <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">return</span> start;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findRotation</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> start = <span class="number">0</span>, end = nums.length, result = (end - start) / <span class="number">2</span>, target = nums[<span class="number">0</span>];</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 取出第一个元素进行比较，如果是大于该元素，说明切分点在中点后面，如果小于该元素，则切分点在中点前面</span></span><br><span class="line">        <span class="keyword">while</span> (result &gt; start &amp;&amp; nums[result] &gt; nums[result - <span class="number">1</span>])&#123;</span><br><span class="line">            <span class="keyword">if</span> (target &gt; nums[result])&#123;</span><br><span class="line">                end = result;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (target &lt; nums[result])&#123;</span><br><span class="line">                start = result;</span><br><span class="line">            &#125;</span><br><span class="line">            result = (end + start) / <span class="number">2</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (start == result)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>




          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/11/15/LeetCode-32/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="影决">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平凡小札">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2019/11/15/LeetCode-32/" itemprop="url">LeetCode-32</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-11-15T23:56:42+08:00">
                2019-11-15
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/算法/" itemprop="url" rel="index">
                    <span itemprop="name">算法</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h2 id="A032-Longest-Valid-Parentheses"><a href="#A032-Longest-Valid-Parentheses" class="headerlink" title="A032 Longest Valid Parentheses"></a>A032 Longest Valid Parentheses</h2><p><a href="https://leetcode-cn.com/problems/longest-valid-parentheses/" target="_blank" rel="noopener">原文链接</a></p>
<pre><code>Given a string containing just the characters &apos;(&apos; and &apos;)&apos;, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: &quot;(()&quot;
Output: 2
Explanation: The longest valid parentheses substring is &quot;()&quot;
Example 2:

Input: &quot;)()())&quot;
Output: 4
Explanation: The longest valid parentheses substring is &quot;()()&quot;</code></pre><p>分析： </p>
<pre><code>1. 找出所有未匹配的括号字符
2. 计算出所有的有效括号字符长度，也就是相邻无效括号字符的序号相减</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">longestValidParentheses</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (s == <span class="keyword">null</span> || s.length() == <span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="comment">// 存放括号中两个匹配括号的位置</span></span><br><span class="line">        <span class="comment">// HashMap&lt;Integer, Integer&gt; hashMap = new HashMap&lt;&gt;();</span></span><br><span class="line">        <span class="comment">// 存储(的序号</span></span><br><span class="line">        List&lt;Integer&gt; list = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        <span class="comment">// 存储不符合条件的字符</span></span><br><span class="line">        List&lt;Integer&gt; list1 = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; s.length(); i++)&#123;</span><br><span class="line">            <span class="keyword">char</span> c = s.charAt(i);</span><br><span class="line">            <span class="keyword">if</span> (c == <span class="string">'('</span>)&#123;</span><br><span class="line">                list.add(i);</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (c == <span class="string">')'</span>)&#123;</span><br><span class="line">                <span class="keyword">if</span> (list.size() == <span class="number">0</span>)&#123;</span><br><span class="line">                    list1.add(i);</span><br><span class="line">                &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="comment">// hashMap.put(list.get(list.size() - 1), i);</span></span><br><span class="line">                    list.remove((<span class="keyword">int</span>)list.size() - <span class="number">1</span>);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (list.size() &gt; <span class="number">0</span>)&#123;</span><br><span class="line">            list1.addAll(list);</span><br><span class="line">        &#125;</span><br><span class="line">        Collections.sort(list1);</span><br><span class="line">        <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; list1.size() - <span class="number">1</span>; i++)&#123;</span><br><span class="line">            <span class="keyword">int</span> tmp = list1.get(i + <span class="number">1</span>) - list1.get(i) - <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">if</span> (tmp &gt; res)&#123;</span><br><span class="line">                res = tmp;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (list1.size() != <span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span> (list1.get(<span class="number">0</span>) &gt; res)&#123;</span><br><span class="line">                res = list1.get(<span class="number">0</span>);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (s.length() - <span class="number">1</span> - list1.get(list1.size() - <span class="number">1</span>) &gt; res)&#123;</span><br><span class="line">                res = s.length() - <span class="number">1</span> - list1.get(list1.size() - <span class="number">1</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (list1.size() == <span class="number">0</span>)&#123;</span><br><span class="line">            res = s.length();</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// System.out.println(list1);</span></span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>




          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/11/14/Java面试总结/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="影决">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平凡小札">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2019/11/14/Java面试总结/" itemprop="url">Java面试总结</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-11-14T21:46:03+08:00">
                2019-11-14
              </time>
            

            

            
          </span>

          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h2 id="struts2的运行流程"><a href="#struts2的运行流程" class="headerlink" title="struts2的运行流程"></a>struts2的运行流程</h2><p><img src="https://gitee.com/simfg/blog-pic/raw/master/pictures/struts2RunnningProcess.jpg" alt="struts2的运行流程图"></p>
<ol>
<li>用户请求，通过URL在web.xml中寻找对应的请求</li>
<li>寻找到请求后，FilterDispatch根据这个请求找到相应的FilterChain，这个FilterChain包含了一系列的Filter</li>
<li>执行完这些Filter后，查看是否存在拦截器，如果存在则执行，且其中一个拦截器返回false，那么便不会执行后续操作了，</li>
<li>ActionProxy通过反射创建Servlet实例，然后执行相应的方法，默认是执行execute方法</li>
<li>根据方法执行的返回结果生成相应的jsp页面，然后由服务器对jsp进行翻译转换成html返回给用户</li>
</ol>
<h2 id="拦截器与过滤器"><a href="#拦截器与过滤器" class="headerlink" title="拦截器与过滤器"></a>拦截器与过滤器</h2><p>过滤器，是在java web中，传入的request,response提前过滤掉一些信息，或者提前设置一些参数，然后再传入servlet或者struts的action进行业务逻辑，比如过滤掉非法url（不是login.do的地址请求，如果用户没有登陆都过滤掉）,或者在传入servlet或者struts的action前统一设置字符集，或者去除掉一些非法字符.</p>
<p>拦截器，是在面向切面编程的就是在你的service或者一个方法，前调用一个方法，或者在方法后调用一个方法比如动态代理就是拦截器的简单实现，在你调用方法前打印出字符串（或者做其它业务逻辑的操作），也可以在你调用方法后打印出字符串，甚至在你抛出异常的时候做业务逻辑的操作。</p>
<p>区别：</p>
<ol>
<li>拦截器是基于java的反射机制的，而过滤器是基于函数回调。</li>
<li>拦截器不依赖与servlet容器，过滤器依赖与servlet容器。</li>
<li>拦截器只能对action请求起作用，而过滤器则可以对几乎所有的请求起作用。</li>
<li>拦截器可以访问action上下文、值栈里的对象，而过滤器不能访问。</li>
<li>在action的生命周期中，拦截器可以多次被调用，而过滤器只能在容器初始化时被调用一次</li>
</ol>
<h2 id="拦截器与过滤器的基本实现"><a href="#拦截器与过滤器的基本实现" class="headerlink" title="拦截器与过滤器的基本实现"></a>拦截器与过滤器的基本实现</h2><p>拦截器：</p>
<ol>
<li>在struts2.xml中的interceptors标签下定义</li>
</ol>
<p><code>&lt;interceptor name=&quot;filterIPInterceptor&quot; class=&quot;com.xxxx.web.FilterIPActionInterceptor&quot; /&gt;</code></p>
<p><code>&lt;interceptor-ref name=&quot;filterIPInterceptor&quot; /&gt;</code></p>
<ol start="2">
<li>自定义拦截器对象，继承<code>AbstractInterceptor</code>，在intercept方法中编写拦截逻辑，如果通过必须执行invocation（intercept方法的参数，ActionInvocation）的invoke方法；</li>
</ol>
<p>过滤器：</p>
<ol>
<li><p>在web.xml中配置Filter</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">&lt;filter&gt;</span><br><span class="line">&lt;filter-name&gt;Redirect Filter&lt;/filter-name&gt;</span><br><span class="line">&lt;filter-class&gt;com.xx.filter.RedirectFilter&lt;/filter-class&gt;</span><br><span class="line">&lt;/filter&gt;</span><br><span class="line"></span><br><span class="line">&lt;filter-mapping&gt;</span><br><span class="line">&lt;filter-name&gt;Redirect Filter&lt;/filter-name&gt;</span><br><span class="line">&lt;url-pattern&gt;/xx/xx/*&lt;/url-pattern&gt;</span><br><span class="line">&lt;/filter-mapping&gt;</span><br></pre></td></tr></table></figure>
</li>
<li><p>自定义过滤器类，实现<code>Filter</code>接口，实现doFilter方法，方法参数为ServletRequest和ServletResponse </p>
</li>
</ol>
<h2 id="spring-mvc的运行流程"><a href="#spring-mvc的运行流程" class="headerlink" title="spring mvc的运行流程"></a>spring mvc的运行流程</h2><p><img src="https://gitee.com/simfg/blog-pic/raw/master/pictures/springmvcRunningProcess.jpg" alt="spring mvc运行流程图"><br>SpringMVC框架是以请求为驱动，围绕Servlet设计，将请求发给控制器，然后通过模型对象，分派器来展示请求结果视图。其中核心类是DispatcherServlet，它是一个Servlet，顶层是实现的Servlet接口</p>
<h2 id="struts2与spring-mvc"><a href="#struts2与spring-mvc" class="headerlink" title="struts2与spring mvc"></a>struts2与spring mvc</h2><ol>
<li><p>框架机制：</p>
<p> spring mvc 和 struts2的加载机制不同：spring mvc的入口是servlet（DispatchServlet），而struts2是filter（StrutsPrepareAndExecuteFilter）</p>
<ul>
<li><p>servlet：servlet是一种运行服务器端的Java应用程序，具有独立于平台和协议的特性，并且可以动态的生成web页面，它工作在客户端请求与服务器响应的中间层。</p>
</li>
<li><p>filter：filter是一个可以复用的代码片段，可以用来转换HTTP请求、响应和头信息。Filter不像Servlet，它不能产生一个请求或者响应，它只是修改对某一资源的请求，或者修改从某一的响应。</p>
</li>
</ul>
</li>
<li><p>拦截机制：<br> struts2：</p>
<ul>
<li>Struts2框架是类级别的拦截，每次请求就会创建一个Action，和Spring整合时Struts2的ActionBean注入作用域是原型模式prototype（否则会出现线程并发问题），然后通过setter，getter吧request数据注入到属性。</li>
<li>Struts2中，一个Action对应一个request，response上下文，在接收参数时，可以通过属性接收，这说明属性参数是让多个方法共享的。</li>
<li>Struts2中Action的一个方法可以对应一个url，而其类属性却被所有方法共享，这也就无法用注解或其他方式标识其所属方法了<br>spring mvc：</li>
<li>SpringMVC是方法级别的拦截，一个方法对应一个Request上下文，所以方法直接基本上是独立的，独享request，response数据。而每个方法与一个url对应，参数的传递是直接注入到方法中的，是方法所独有的。处理结果通过ModeMap返回给框架。</li>
<li>在Spring整合时，SpringMVC的Controller Bean默认单例模式Singleton，所以默认对所有的请求，只会创建一个Controller，因为没有共享的属性，所以是线程安全的，如果要改变默认的作用域，需要添加@Scope注解修改。</li>
</ul>
</li>
<li><p>性能方面：</p>
<p> spring mvc实现了零配置，由于spring mvc基于方法的拦截，有加载一次单例模式bean注入。而struts2是类级别的拦截，每次请求对应实例一个新的Action，需要加载所有的属性值注入，所以，spring mvc开发效率和性能高于struts2。</p>
</li>
<li><p>拦截机制:</p>
<p> struts2有自己的拦截Interceptor机制，spring mvc这是用的是独立的Aop方式，这样导致struts2的配置文件量还是比spring mvc大。</p>
</li>
</ol>
<ol start="5">
<li><p>配置方面</p>
<p> spring mvc和spring是无缝的。从这个项目的管理和安全上也比struts2高（当然struts2也可以通过不同的目录结构和相关配置做到spring mvc一样的效果，但是需要xml配置的地方不少）。</p>
</li>
<li><p>设计思想</p>
<p> struts2更加符合OOP的编程思想， spring mvc就比较谨慎，在servlet上扩展。</p>
</li>
<li><p>集成方面</p>
<p> spring mvc集成了Ajax，使用非常方便，只需一个注解@ResponseBody就可以实现，然后直接返回响应文本即可，而struts2拦截器集成了Ajax，在Action中处理时一般必须安装插件或者自己写代码集成进去，使用起来也相对不方便。</p>
</li>
</ol>
<h2 id="spring"><a href="#spring" class="headerlink" title="spring"></a>spring</h2><ol>
<li><p>什么是spring framework</p>
<ul>
<li>spring是一个开源框架，旨在降低应用程序开发的复杂度</li>
<li>是轻量级、低耦合的框架</li>
<li>具有分层体系结构，允许用户自由选择组件</li>
<li>可以集成其他框架，如hibernate、struts2、mybaits等</li>
</ul>
</li>
<li><p>spring framework的优点</p>
<ul>
<li>具有分层体系结构，用户可以根据自己的需求选择组件</li>
<li>支持pojo编程（plain old java object），从而可以持续集成和可测试性</li>
<li>由于依赖注入和控制反转，JDBC的开发得到简化</li>
<li>免费开源的框架</li>
</ul>
</li>
<li><p>spring framework的功能</p>
<ul>
<li>IOC，控制反转，负责创建和管理对象（Bean）的生命周期和配置</li>
<li>AOP，面向切面编程可以将应用业务逻辑和系统服务分离，以实现高内聚</li>
<li>MVC，对 web 应用提供了高度可配置性，其他框架的集成也十分方便</li>
</ul>
</li>
<li><p>spring framework常见的模块有哪些<br><img src="https://gitee.com/simfg/blog-pic/raw/master/pictures/springmodules.jpg" alt="spring modules"></p>
<ul>
<li>Spring 核心容器 – 该层基本上是 Spring Framework 的核心。它包含以下模块：Spring Core、Spring Bean、SpEL (Spring Expression Language)、Spring Context</li>
<li>数据访问/集成 – 该层提供与数据库交互的支持。它包含以下模块：JDBC (Java DataBase Connectivity)、ORM (Object Relational Mapping)、OXM (Object XML Mappers)、JMS (Java Messaging Service)、Transaction</li>
<li>Web – 该层提供了创建 Web 应用程序的支持。它包含以下模块：Web、Web – Servlet、Web – Socket、Web – Portlet</li>
<li>AOP – 该层支持面向切面编程</li>
<li>Instrumentation – 该层为类检测和类加载器实现提供支持。</li>
<li>Test – 该层为使用 JUnit 和 TestNG 进行测试提供支持。</li>
<li>几个杂项模块:Messaging – 该模块为 STOMP 提供支持。它还支持注解编程模型，该模型用于从 WebSocket 客户端路由和处理 STOMP 消息；Aspects – 该模块为与 AspectJ 的集成提供支持。</li>
</ul>
</li>
<li><p>IOC</p>
<ul>
<li>spring 框架的核心是 spring 容器。容器创建对象，将它们装配在一起，配置它们并管理它们的完整生命周期。spring 容器使用依赖注入来管理组成应用程序的组件。容器通过读取提供的配置元数据来接收对象进行实例化，配置和组装的指令。该元数据可以通过 XML，Java 注解或 Java 代码提供</li>
<li>通常，依赖注入可以通过三种方式完成，即：构造方法注入、setter方法注入及其接口注入，在spring中，只有构造方法注入和setter方法注入</li>
<li>IOC的好处<ol>
<li>最小化应用程序中的代码量，降低应用程序开发复杂度</li>
<li>以最小的影响和最少的侵入机制促进松耦合</li>
<li>支持即时的实例化和延迟加载服务</li>
</ol>
</li>
<li>实现原理：工厂模式加反射机制</li>
</ul>
</li>
<li><p>spring bean</p>
<ul>
<li>什么是spring bean<ol>
<li>构成用户应用程序主干的对象</li>
<li>由 Spring IoC 容器实例化，配置，装配和管理</li>
<li>基于用户提供给容器的配置元数据创建</li>
</ol>
</li>
<li>spring中配置bean的三种方式<ol>
<li>基于 xml 配置</li>
<li>基于注解配置，默认情况下，Spring 容器中未打开注解装配；<code>&lt;context:annotation-config\&gt;</code>; 注解包含了：@Component/@Repository/@Service/@Controller</li>
<li>基于Java API配置，通过使用 @Bean 和 @Configuration 来实现。<pre><code>@Configuration
class Config{
 @Bean
 public Bean getBean(){
     return new Bean();
 }
}</code></pre></li>
</ol>
</li>
<li>bean scope<ol>
<li>Singleton - 每个 Spring IoC 容器仅有一个单实例。</li>
<li>Prototype - 每次请求都会产生一个新的实例。</li>
<li>Request - 每一次 HTTP 请求都会产生一个新的实例，并且该 bean 仅在当前 HTTP 请求内有效。</li>
<li>Session - 每一次 HTTP 请求都会产生一个新的 bean，同时该 bean 仅在当前 HTTP session 内有效。</li>
<li>Global-session - 类似于标准的 HTTP Session 作用域，不过它仅仅在基于 portlet 的 web 应用中才有意义。Portlet 规范定义了全局 Session 的概念，它被所有构成某个 portlet web 应用的各种不同的 portlet 所共享。在 global session 作用域中定义的 bean 被限定于全局 portlet Session 的生命周期范围内。如果你在 web 中使用 global session 作用域来标识 bean，那么 web 会自动当成 session 类型来使用。<br>仅当用户使用支持 Web 的 ApplicationContext 时，最后三个才可用</li>
</ol>
</li>
</ul>
</li>
<li><p>常见注解</p>
<ol>
<li>@Component/@Repository/@Service/@Controller、</li>
<li>@Autowired：用于在 setter 方法，构造函数，具有任意名称或多个参数的属性或方法上自动装配 bean</li>
<li>@Required：必须在配置时使用 bean 定义中的显式属性值或使用自动装配填充受影响的 bean 属性</li>
<li>@Qualifier：当创建多个相同类型的 bean 并希望仅使用属性装配其中一个 bean 时，可以使用@Qualifier 注解和 @Autowired 通过指定应该装配哪个确切的 bean 来消除歧义</li>
<li>@RequestMapping ：用于将特定 HTTP 请求方法映射到将处理相应请求的控制器中的特定类/方法，类级别：映射请求的 URL；方法级别：映射 URL 以及 HTTP 请求方法</li>
<li>@ResponseBody：返回json类型的数据</li>
</ol>
</li>
<li><p>AOP</p>
<ol>
<li>什么是AOP<br> AOP(Aspect-Oriented Programming), 即 面向切面编程, 它与 OOP( Object-Oriented Programming, 面向对象编程) 相辅相成, 提供了与 OOP 不同的抽象软件结构的视角。在 OOP 中, 我们以类(class)作为我们的基本单元, 而 AOP 中的基本单元是 Aspect(切面)</li>
<li>什么是Apsect<ul>
<li>aspect 由 pointcount 和 advice 组成, 它既包含了横切逻辑的定义, 也包括了连接点的定义.</li>
<li>AOP 的工作重心在于如何将增强编织目标对象的连接点上, 这里包含两个工作:<ul>
<li>如何通过 pointcut 和 advice 定位到特定的 joinpoint 上</li>
<li>如何在 advice 中编写切面代码.</li>
</ul>
</li>
<li>可以简单地认为, 使用 @Aspect 注解的类就是切面.</li>
</ul>
</li>
<li>joinpoint/pointcut/advice<ul>
<li>joinpoint 总是方法的执行点</li>
<li>pointcut，与joinpoint进行匹配，符合要求则对该joinpoint进行advice应用</li>
<li>特定 joinpoint 处的 Aspect 所采取的动作称为 advice<ul>
<li>Before - 这些类型的 Advice 在 joinpoint 方法之前执行，并使用 @Before 注解标记进行配置。</li>
<li>After Returning - 这些类型的 Advice 在连接点方法正常执行后执行，并使用@AfterReturning 注解标记进行配置。</li>
<li>After Throwing - 这些类型的 Advice 仅在 joinpoint 方法通过抛出异常退出并使用 @AfterThrowing 注解标记配置时执行。</li>
<li>After (finally) - 这些类型的 Advice 在连接点方法之后执行，无论方法退出是正常还是异常返回，并使用 @After 注解标记进行配置。</li>
<li>Around - 这些类型的 Advice 在连接点之前和之后执行，并使用 @Around 注解标记进行配置。<br><a href="https://www.cnblogs.com/Ti1077/p/9488251.html" target="_blank" rel="noopener">详细内容参考</a></li>
</ul>
</li>
</ul>
</li>
</ol>
</li>
</ol>
<h2 id="maven的5个基本生命周期"><a href="#maven的5个基本生命周期" class="headerlink" title="maven的5个基本生命周期"></a>maven的5个基本生命周期</h2><p>clean/compile/test/package/install</p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/11/07/LeetCode-1-10/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="影决">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平凡小札">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2019/11/07/LeetCode-1-10/" itemprop="url">LeetCode 1-10</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-11-07T23:56:42+08:00">
                2019-11-07
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/算法/" itemprop="url" rel="index">
                    <span itemprop="name">算法</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h2 id="A001-Two-Sum"><a href="#A001-Two-Sum" class="headerlink" title="A001 Two Sum"></a>A001 Two Sum</h2><p><a href="https://leetcode-cn.com/problems/two-sum/" target="_blank" rel="noopener">原文链接</a></p>
<blockquote>
<p>Given an array of integers, return indices of the two numbers such that they add up to a specific target.</p>
<p>You may assume that each input would have exactly one solution, and you may not use the same element twice.</p>
<p>Example:</p>
<p>Given nums = [2, 7, 11, 15], target = 9,</p>
<p>Because nums[0] + nums[1] = 2 + 7 = 9,</p>
<p>return [0, 1].</p>
</blockquote>
<p>分析： </p>
<pre><code>1. 声明一个HashMap（key为当前数字，value为当前数字在数组中的序号）
2. 循环数组，循环体如下：（当前数字使用cur表示）
    1. 查看target-cur是否存在与当前map的key中；存在则返回当前的序号和target-cur的序号
    2. 将当前数字添加字HashMap中
3. 返回[-1, -1]</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123;</span><br><span class="line">    HashMap&lt;Integer, Integer&gt; hashMap = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> result[] = <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;-<span class="number">1</span>, -<span class="number">1</span>&#125;;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (nums == <span class="keyword">null</span> || nums.length &lt; <span class="number">2</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; nums.length; i++)&#123;</span><br><span class="line">        <span class="keyword">int</span> j = target - nums[i];</span><br><span class="line">        <span class="keyword">if</span> (hashMap.containsKey(j))&#123;</span><br><span class="line">            result[<span class="number">0</span>] = hashMap.get(j);</span><br><span class="line">            result[<span class="number">1</span>] = i;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        hashMap.put(nums[i], i);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="A002-Add-Two-Numbers"><a href="#A002-Add-Two-Numbers" class="headerlink" title="A002 Add Two Numbers"></a>A002 Add Two Numbers</h2><p><a href="https://leetcode-cn.com/problems/add-two-numbers/" target="_blank" rel="noopener">原文链接</a></p>
<blockquote>
<p>You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.</p>
<p>You may assume the two numbers do not contain any leading zero, except the number 0 itself.</p>
<p>Example:</p>
<p>Input: (2 -&gt; 4 -&gt; 3) + (5 -&gt; 6 -&gt; 4)</p>
<p>Output: 7 -&gt; 0 -&gt; 8</p>
<p>Explanation: 342 + 465 = 807.</p>
</blockquote>
<p>分析：</p>
<pre><code>1. 声明变量，其中res表示结果变量，cur表示当前节点，a、b分别表示l1和l2的当前节点，sum表示当前的结果值
2. 循环l1和l2，控制条件为当前节点不为null
    1. 分别判断a和b节点是否为空，因为两个ListNode长度可能不一，如果不为空，将该节点的值加值sum上
    2. a和b当前节点完成后，生成cur的下一节点，这个节点的值为sum%10
    3. 切换cur的节点，然后对sum更新，便于下一个节点计算，注意：如果存在进位，也就是sum这时候就会大于10，sum/10之后就会等于1，这个进位会自动存储到下一次循环
3. 判断当前sum是否为1，如果为1，说明在进行最后一次相加时存在进位，那么这时候就需要新生成一个节点
4. 返回res.next，因为res的第一个值为0</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition for singly-linked list.</span></span><br><span class="line"><span class="comment"> * public class ListNode &#123;</span></span><br><span class="line"><span class="comment"> *     int val;</span></span><br><span class="line"><span class="comment"> *     ListNode next;</span></span><br><span class="line"><span class="comment"> *     ListNode(int x) &#123; val = x; &#125;</span></span><br><span class="line"><span class="comment"> * &#125;</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> ListNode <span class="title">addTwoNumbers</span><span class="params">(ListNode l1, ListNode l2)</span> </span>&#123;</span><br><span class="line">    ListNode res = <span class="keyword">new</span> ListNode(<span class="number">0</span>);</span><br><span class="line">    ListNode cur = res;</span><br><span class="line">    ListNode a = l1, b = l2;</span><br><span class="line">    <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(a != <span class="keyword">null</span> || b != <span class="keyword">null</span>)&#123;</span><br><span class="line">        <span class="keyword">if</span>(a != <span class="keyword">null</span>)&#123;</span><br><span class="line">            sum += a.val;</span><br><span class="line">            a = a.next;</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        <span class="keyword">if</span>(b != <span class="keyword">null</span>)&#123;</span><br><span class="line">            sum += b.val;</span><br><span class="line">            b = b.next;</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        cur.next = <span class="keyword">new</span> ListNode(sum % <span class="number">10</span>);</span><br><span class="line">        cur = cur.next;</span><br><span class="line">        sum /= <span class="number">10</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(sum == <span class="number">1</span>)&#123;</span><br><span class="line">        cur.next = <span class="keyword">new</span> ListNode(<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res.next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="A003-Longest-Substring-Without-Repeating-Characters"><a href="#A003-Longest-Substring-Without-Repeating-Characters" class="headerlink" title="A003 Longest Substring Without Repeating Characters"></a>A003 Longest Substring Without Repeating Characters</h2><p><a href="https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/" target="_blank" rel="noopener">原文链接</a></p>
<blockquote>
<p>Given a string, find the length of the longest substring without repeating characters.</p>
<p>Example 1:</p>
<p>Input: “abcabcbb”</p>
<p>Output: 3 </p>
<p>Explanation: The answer is “abc”, with the length of 3. </p>
<p>Example 2:</p>
<p>Input: “bbbbb”</p>
<p>Output: 1</p>
<p>Explanation: The answer is “b”, with the length of 1.</p>
<p>Example 3:</p>
<p>Input: “pwwkew”</p>
<p>Output: 3</p>
<p>Explanation: The answer is “wke”, with the length of 3. </p>
<p>Note that the answer must be a substring, “pwke” is a subsequence and not a substring.</p>
</blockquote>
<p>分析：</p>
<pre><code>1. 声明res，用于存储当前最大子串的长度，声明map，其中key为当前字符，value为当前字符的序号
2. 遍历当前字符串，其中j标识了当前子串中的第一个字符位置
    1. 查看map中key是否包含当前字符，如果包含更新j的值，j的值为map中value的值加一，也就是表示在当前子串中与当前字符一样的字符位置后一位
    2. 将当前字符和字符位置添加至map中
    3. 更新res
3. 返回res</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">lengthOfLongestSubstring</span><span class="params">(String s)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (s == <span class="keyword">null</span> || s.length() == <span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    HashMap&lt;Character, Integer&gt; map = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>, j = <span class="number">0</span>; i &lt; s.length(); i++)&#123;</span><br><span class="line">        <span class="keyword">if</span> (map.keySet().contains(s.charAt(i)))&#123;</span><br><span class="line">            j = Math.max(j, map.get(s.charAt(i)) + <span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        map.put(s.charAt(i), i);</span><br><span class="line">        res = Math.max(res, i - j + <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="A004-Median-of-Two-Sorted-Arrays"><a href="#A004-Median-of-Two-Sorted-Arrays" class="headerlink" title="A004 Median of Two Sorted Arrays"></a>A004 Median of Two Sorted Arrays</h2><p><a href="https://leetcode-cn.com/problems/median-of-two-sorted-arrays/" target="_blank" rel="noopener">原文链接</a></p>
<blockquote>
<p>There are two sorted arrays nums1 and nums2 of size m and n respectively.</p>
<p>Find the median of the two sorted arrays. <strong>The overall run time complexity should be O(log (m+n))</strong>.</p>
<p>You may assume nums1 and nums2 cannot be both empty.</p>
<p>Example 1:</p>
<p>nums1 = [1, 3]<br>nums2 = [2]</p>
<p>The median is 2.0</p>
<p>Example 2:</p>
<p>nums1 = [1, 2]<br>nums2 = [3, 4]</p>
<p>The median is (2 + 3)/2 = 2.5</p>
</blockquote>
<p>分析：</p>
<pre><code>1. 假设nums1的长度总是小于nums2的长度
2. 声明各种变量，其中cut1和cut2表示两个数组切分的位置，cutL和cutR表示第一个数组基于上一次切分位置当前切分位置左右的元素个数（详解见下）
     cut1 = 2, cutL = 3, cutR = 1
1 7 8 | 9 
2 3 | 6 10 13
   cut2 = 2 
3. 循环，条件为cut1小于等于数组nums1的长度
    1. 更新cut1，（二分法更新 cut1 = (cutR - cutL)/2 + cutL）
    2. 更新cut2，其中cut1 + cut2 = len/2 这是固定的，因为寻找中位数，那么这个数的左右两边的树的个数就是相同的
    3. 计算切分位置的左右值，分别记为L1/R1/L2/R2
        L1 = 8, R1 = 9
        1 7 8 | 9 
        2 3 | 6 10 13
        L2 = 3, R2 = 6
    4. 处理一种极端情况，那就是如果切分位置为最开始，那么L1或者L2的值就不存在，那么这时候就需要赋值为无穷小，
        因为这L和R的值只是用来做判断，且在取值时时取L1L2中最大R1R2中最小的，也就不会去到这个无穷的值了，自然如果切分位置为末尾，那么R1或R2的值为无穷大
    5. 如果L1大于R2了，说明第一个切分位置应该往左移，这时候L1就会变小，因为这两个数组为有序数组，自然这时候第二个切分位置就会往右移，
        R2就会变大，就会往L1小于R2的趋势发展，因为在理想切分位置下，应该满足L1 &lt; R2 &amp;&amp; L2 &lt; R1，这就说明在切分位置的左边元素都小于切分位置的右边元素，那么中位数就是在L1/L2/R1/R2四个数字中
        操作：更新cutR = cut1 - 1，那么下一次cut1的位置就由（cutL -- cut1 -- cutR）变为（cutL - cut1 - cutR --），其中‘-’表示元素，cutL/cut1/cutR均代表位置
     cutL cut1 cutR
        |---|---|
        |-|-|----
    cutL cut1 cutR
    6. 如果L2大于R1，那么第一个切分位置应该往右移，也就是cutL = cut1 + 1
    7. 如果达到理想情况，那么这时候获取中位数
        1. 如果数组总长度为偶数，那么去左边最大右边最小的值，然后除以2便是结果
        2. 如果是奇数的话，那么结果就是右边的最小值</code></pre><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">double</span> <span class="title">findMedianSortedArrays</span><span class="params">(<span class="keyword">int</span>[] nums1, <span class="keyword">int</span>[] nums2)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (nums1.length &gt; nums2.length)&#123;</span><br><span class="line">        <span class="keyword">return</span> findMedianSortedArrays(nums2, nums1);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> len = nums1.length + nums2.length;</span><br><span class="line">    <span class="keyword">int</span> cut1 = <span class="number">0</span>, cut2 = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> cutL = <span class="number">0</span>, cutR = nums1.length;</span><br><span class="line">    <span class="keyword">while</span> (cut1 &lt;= nums1.length)&#123;</span><br><span class="line">        cut1 = (cutR - cutL)/<span class="number">2</span> + cutL;</span><br><span class="line">        cut2 = len / <span class="number">2</span> - cut1;</span><br><span class="line">        <span class="keyword">double</span> L1 = (cut1 == <span class="number">0</span>) ? Integer.MIN_VALUE : nums1[cut1 - <span class="number">1</span>];</span><br><span class="line">        <span class="keyword">double</span> L2 = (cut2 == <span class="number">0</span>) ? Integer.MIN_VALUE : nums2[cut2 - <span class="number">1</span>];</span><br><span class="line">        <span class="keyword">double</span> R1 = (cut1 == nums1.length) ? Integer.MAX_VALUE : nums1[cut1];</span><br><span class="line">        <span class="keyword">double</span> R2 = (cut2 == nums2.length) ? Integer.MAX_VALUE : nums2[cut2];</span><br><span class="line">        <span class="keyword">if</span> (L1 &gt; R2)&#123;</span><br><span class="line">            cutR = cut1 - <span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span> (L2 &gt; R1)&#123;</span><br><span class="line">            cutL = cut1 + <span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">if</span> (len % <span class="number">2</span> == <span class="number">0</span>)&#123;</span><br><span class="line">                L1 = L1 &gt; L2 ? L1 : L2;</span><br><span class="line">                R1 = R1 &lt; R2 ? R1 : R2;</span><br><span class="line">                <span class="keyword">return</span> (L1 + R1) / <span class="number">2</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                R1 = (R1 &lt; R2) ? R1 : R2;</span><br><span class="line">                <span class="keyword">return</span> R1;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>




          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/11/06/Java-笔记（一）/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="影决">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平凡小札">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2019/11/06/Java-笔记（一）/" itemprop="url">Java 笔记（一）</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-11-06T20:01:52+08:00">
                2019-11-06
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/Java-笔记/" itemprop="url" rel="index">
                    <span itemprop="name">Java 笔记</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h2 id="Object的方法"><a href="#Object的方法" class="headerlink" title="Object的方法"></a>Object的方法</h2><ol>
<li><p>equals(): 比较两个对象，默认时进行地址的比较；</p>
</li>
<li><p>hashCode(): 获取对象的散列值，当需要比较多个对象时，使用equals方法耗时，hashCode可以大大节省时间；</p>
</li>
<li><p>toString(): 将对象转换为字符串，默认输出为：对象路径@对象内存地址</p>
</li>
<li><p>clone(): 克隆对象，对象需要实现Cloneable接口，否则会出现CloneNotSupportedException，同时注意区分对象赋值与对象克隆、浅克隆与深克隆；</p>
</li>
<li><p>getClass(): 获取当前对象的Class类，主要用于反射；</p>
</li>
<li><p>notify()/notifyAll(): 唤醒在此对象监视器上的线程；</p>
</li>
<li><p>wait()/waitAll(): 当前线程进入等待；</p>
</li>
<li><p>finalize(): 当前对象回收时执行该方法，但是不能保证一定会执行；</p>
</li>
<li><p>native方法和非native方法：native方法并不是使用java语言进行实现，而是由jvm内部实现，也就是使用c++语言进行实现的，根据不同主机执行的方式不一样，另外native方法一般比非native方法执行快；</p>
</li>
</ol>
<p><a href="https://blog.csdn.net/qq_34115898/article/details/83270519" target="_blank" rel="noopener">参考博客</a></p>
<h2 id="Object的wait方法与Thread的sleep方法的区别"><a href="#Object的wait方法与Thread的sleep方法的区别" class="headerlink" title="Object的wait方法与Thread的sleep方法的区别"></a>Object的wait方法与Thread的sleep方法的区别</h2><ol>
<li><p>wait()来自于Object类而sleep来自于Thread类</p>
</li>
<li><p>sleep没有释放锁，但是wait释放了锁（使得其他线程可以使用同步控制块或者方法锁）</p>
</li>
<li><p>wait，waitAll，notify和notifyAll只能在同步控制方法或者同步控制块使用（在synchronized方法或者block中），而sleep能在各个地方使用</p>
</li>
<li><p>sleep必须捕获异常，但是wait不用</p>
</li>
<li><p>sleep让一个线程睡眠，等待一段时间后，自动醒来进入可运行状态，不会马上进入运行状态，因为线程调度机制恢复线程也需要时间。如果调用interrup方法，则会抛出InterruptedException。如果不捕获这个异常，那么会进入TERMINATED状态。如果捕获这个异常，那么可以在catch中继续执行后面的代码。如果线程并不处于wait，sleep，join状态时，调用interrupt方法线程不会抛出InterruptedException。</p>
</li>
<li><p>sleep是静态方法，只会让当前线程sleep，t.sleep()并不会让t进入sleep</p>
</li>
</ol>
<p><a href="https://www.cnblogs.com/ylxn/p/10395315.html" target="_blank" rel="noopener">参考博客</a></p>
<h2 id="异常"><a href="#异常" class="headerlink" title="异常"></a>异常</h2><p>异常的顶级父类：Throwable，其实现了Serializable接口；</p>
<p>Error类和Exception类：继承Throwable，Error表示程序运行环境出现异常，如OutOfMemoryError,StackOverFlowError；Exception表示程序运行时出现异常，由显式异常（RuntimeException）和隐式异常（IOException、SQLException）之分；</p>
<p>常见异常类：</p>
<pre><code>1. ArithmeticException： 除数为0；

2. ClassCastException: 类型转换错误；

3. NullPointException: 访问为初始化对象的方法；

4. IndexOutOfBoundsException: 数组下标越界或者字符串访问越界；

5. ClassNotFoundException: 未找到指定类或者接口；

6. NumberFormatException： 字符转换为数字类型异常，如Integer.valueOf(&quot;a&quot;);

7. CloneNotSupportedException: 使用对象的克隆方法，但是对象没有实现Cloneable接口；

8. InterruptedException: 线程中断异常，如果在线程处于sleep/wait/join状态下，调用interrupt方法则会导致该异常，在调用Thread.sleep()方法时必须捕捉该异常；</code></pre>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/10/31/工作日记-2019-10-13/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="影决">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平凡小札">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2019/10/31/工作日记-2019-10-13/" itemprop="url">工作日记:2019-10-13</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-10-31T20:40:45+08:00">
                2019-10-31
              </time>
            

            

            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/工作日记/" itemprop="url" rel="index">
                    <span itemprop="name">工作日记</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h2 id="spring-FactoryBean接口"><a href="#spring-FactoryBean接口" class="headerlink" title="spring FactoryBean接口"></a>spring FactoryBean接口</h2><p>一句话总结：可以自定义某个bean的创建过程，主要的接口方法包括了：<code>getObject</code>,<code>getObjectType</code>,<code>isSingleton</code></p>
<p><a href="https://blog.csdn.net/zknxx/article/details/79572387" target="_blank" rel="noopener">参考博客</a></p>
<h2 id="spring-InitializingBean接口"><a href="#spring-InitializingBean接口" class="headerlink" title="spring InitializingBean接口"></a>spring InitializingBean接口</h2><p>一句话总结：在某个bean初始化完成后额外执行部分操作，主要接口方法包括了：<code>afterPropertiesSet</code></p>
<p><a href="https://www.cnblogs.com/study-everyday/p/6257127.html" target="_blank" rel="noopener">参考博客</a></p>
<h2 id="spring-MessageConvert接口"><a href="#spring-MessageConvert接口" class="headerlink" title="spring MessageConvert接口"></a>spring MessageConvert接口</h2><p>一句话总结：在使用JMS过程中，可以对MQ中的消息进行转换</p>
<p><a href="https://www.iteye.com/blog/elim-1900937" target="_blank" rel="noopener">参考博客</a></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <span class="page-number current">1</span><a class="page-number" href="/page/2/">2</a><a class="extend next" rel="next" href="/page/2/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">影决</p>
              <p class="site-description motion-element" itemprop="description">在平凡的生活里做着平凡的事，愿我造就不平凡的未来。</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">14</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">5</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">8</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          

          
          

          
          

          

        </div>
      </section>

      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2019</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">影决</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Mist</a> v5.1.4</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  

  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
<!-- 页面点击小红心 -->
<script type="text/javascript" src="/js/src/clicklove.js"></script>
</html>
